package com.example.demo.arithmetic.datastructure.graph;

import java.util.LinkedList;
import java.util.List;

/**
 * 图的广度优先遍历
 */
public class BFS {

    public static void main(String[] args) {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");

        v1.edges = List.of(new Vertex.Edge(v3, 9), new Vertex.Edge(v2, 7), new Vertex.Edge(v6, 14));
        v2.edges = List.of(new Vertex.Edge(v4, 15));
        v3.edges = List.of(new Vertex.Edge(v4, 11), new Vertex.Edge(v6, 2));
        v4.edges = List.of(new Vertex.Edge(v5, 6));
        v5.edges = List.of();
        v6.edges = List.of(new Vertex.Edge(v5, 9));
//        bfs(v1);
        bfs2(v1);
    }


    public static void bfs(Vertex v) {
//        v.visited=true;
//        for (Vertex.Edge edge : v.edges) {
//            System.out.println(edge.linked.name);
//            if (!edge.linked.visited) {
//                bfs(edge.linked);
//            }
//        }

    }

    /**
     * 非递归实现
     *
     * @param v
     */
    public static void bfs2(Vertex v) {
        // 队列
        LinkedList<Vertex> queue = new LinkedList<>();
        queue.offer(v);
        v.visited = true;
        while (!queue.isEmpty()) {
            Vertex poll = queue.poll();
            System.out.println(poll.name);
            for (Vertex.Edge edge : poll.edges) {
                Vertex linked = edge.linked;
                if (!linked.visited) {
                    linked.visited = true;
                    queue.offer(linked);
                }
            }
        }
    }
}
